#include"stdio.h"
#include"stdlib.h"


#define MaxInt 32767
#define MAX_VEX 20               //最大顶点个数
#define QUEUE_SIZE (MAX_VEX + 1) //队列长度
typedef enum
{
    FALSE,
    TRUE
} boolean;
typedef char VertexType;
typedef struct
{                               //图的邻接矩阵存储结构
    VertexType vexs[MAX_VEX];   //顶点向量
    int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
    int vexnum, arcnum;         //图的当前顶点数和弧数
} MGraph;
boolean visited[MAX_VEX]; //访问标志数组
class Queue
{ //队列类型
public:
    void InitQueue()
    {
        base = (int *)malloc(QUEUE_SIZE * sizeof(int));
        front = rear = 0;
    }
    void EnQueue(int e)
    {
        base[rear] = e;
        rear = (rear + 1) % QUEUE_SIZE;
    }
    void DeQueue(int &e)
    {
        e = base[front];
        front = (front + 1) % QUEUE_SIZE;
    }
    int *base;
    int front;
    int rear;
};
//图 G 中查找元素 c 的位置
int Locate(MGraph G, char c)
{
    for (int i = 0; i < G.vexnum; i++)
        if (G.vexs[i] == c)
            return i;
    return -1;
}
//创建无向网的邻接矩阵存储结构
void CreateUDN(MGraph &G)
{
    int i, j, w, s1, s2;
    char a, b, c, temp;
    printf("输入顶点数和弧数:");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    temp = getchar(); //接收回车
    printf("输入%d 个顶点（以空格做间隔）：\n", G.vexnum);
    for (i = 0; i < G.vexnum; i++)
    { //初始化顶点
        scanf("%c", &G.vexs[i]);
        temp = getchar(); //接收回车
    }
    for (i = 0; i < G.vexnum; i++) //初始化邻接矩阵
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    printf("输入%d 条弧及其权值（以空格做间隔）：\n", G.arcnum);
    for (i = 0; i < G.arcnum; i++)
    { //初始化弧
        printf("输入弧%d:    ", i + 1);
        scanf("%c %c %d%c", &a, &b, &w, &c); //输入一条边依附的顶点和权值
        s1 = Locate(G, a);
        s2 = Locate(G, b);
        G.arcs[s1][s2] = G.arcs[s2][s1] = w;
    }
}
//图 G 中顶点 k 的第一个邻接顶点
int FirstVex(MGraph G, int k)
{
    //请在此填写代码，将该算法补充完整，参见书本或课件相关章节
    if (k >= 0 && k < G.vexnum)
    { //k合理
        for (int i = 0; i < G.vexnum; i++)
            if (G.arcs[k][i] != 0)
                return i;
    }
    return -1;
}
//图 G 中顶点 i 的第 j 个邻接顶点的下一个邻接顶点
int NextVex(MGraph G, int i, int j)
{
    //请在此填写代码，将该算法补充完整，参见书本或课件相关章节
    if (i >= 0 && i < G.vexnum && j >= 0 && j < G.vexnum)
    { //i,j合理
        for (int k = j + 1; k < G.vexnum; k++)
            if (G.arcs[i][k] != 0)
                return k;
    }
    return -1;
}
//广度优先遍历
void BFS(MGraph G)
{
    //请在此填写代码，将该算法补充完整，参见书本或课件相关章节
    int k;
    Queue Q;       //辅助队列Q
    Q.InitQueue(); //初始化队列Q
    for (int v = 0; v < G.vexnum; v++)
        visited[v] = FALSE; //访问标记数组初始化
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i])
        {                      //i尚未访问
            visited[i] = TRUE; //设置已访问标记
            printf("%c", G.vexs[i]);
            Q.EnQueue(i); //i入列
            while (Q.front != Q.rear)
            {                 //如果队列非空
                Q.DeQueue(k); //队头元素出列并置为k
                //设置w为k的第一个邻接点，w不断为除了w之外的下一个邻接点
                for (int w = FirstVex(G, k); w >= 0; w = NextVex(G, k, w))
                    if (!visited[w])
                    {                      //w为k的尚未访问的邻接顶点
                        visited[w] = TRUE; //设置已访问标记
                        printf("->%c", G.vexs[w]);
                        Q.EnQueue(w); //顶点w入队列
                    }
            }
        }
}
//主函数
int main()
{
    MGraph G;
    CreateUDN(G);
    printf("广度优先遍历: ");
    BFS(G);
    printf("\n");
    return 0;
}